package org.example;

// 差分数组
// 前缀和技巧 主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和，核心代码就是下面这段：
// labuladong：https://labuladong.online/algo/data-structure/diff-array/#%E7%AE%97%E6%B3%95%E5%AE%9E%E8%B7%B5
public class DifferentArray {

    static class PrefixSum {
        // 前缀和数组
        int[] preSum;

        // 输入一个数组，构造前缀和
        public PrefixSum(int[] nums) {
            // preSum[0] = 0, 便于计算累加和
            preSum = new int[nums.length + 1];
            // 计算nums的累加和
            for (int i = 1; i < preSum.length; i++) {
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
        }

        // 查询闭区间[left, right]的累加和
        public int sumRange(int left, int right) {
            return preSum[right + 1] - preSum[left];
        }

        // preSum[i]就代表着nums[0..i-1]所有元素的累加和，如果我们相求区间nums[i..j]的累加和，只要计算preSum[j+1]-preSum[i]即可，
        // 而不需要遍历整个区间求和
    }

    // 差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减
    // 比如说，我给你输入一个数组nums，然后又要求给区间nums[2..6]全部加1，再给nums[3..9]全部减3，再给nums[0..4]全部加2，再给...
    // 一通操作猛如虎，然后问你，最后 nums 数组的值是什么？
    // 常规的思路很容易，你让我给区间 nums[i..j] 加上 val，那我就一个 for 循环给它们都加上呗，还能咋样？这种思路的时间复杂度是O(N)
    // 由于这个场景下对 nums 的修改非常频繁，所以效率会很低下。
    //
    // 这里就需要差分数组的技巧，类似前缀和技巧构造的 preSum 数组，我们先对 nums 数组构造一个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差：
    static class Different {
        int[] diff;

        public int[] createDifferent(int[] nums) {
            diff = new int[nums.length];
            // 构造差分数组
            diff[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                diff[i] = nums[i] - nums[i - 1];
            }
            return diff;
        }

        // 通过这个diff差分数组是可以反推出原始数组nums的
        public int[] reverseStep(int[] nums) {
            int[] res = new int[diff.length];
            // 根据差分数组构造结构数组
            res[0] = diff[0];
            for (int i = 1; i < diff.length; i++) {
                res[i] = res[i - 1] + diff[i];
            }
            return res;
        }
        // 这样构造差分数组diff，就可以快速进行区间增减的操作，如果你想对区间nums[i..j]的元素全部加3，那么只需要让diff[i]+=3,然后再让diff[j+1]-=3即可
        // nums {8 ,5, 9, 6, 1}
        // diff {8,-3, 4,-3,-5}
        //          i     j
        // 原理很简单，回想diff数组反推nums数组的过程，diff[i]+=3意味着给nums[i..]所有的元素都加了3，
        // 然后diff[j+1]-=3又意味着对于nums[j+1..]所有元素再减3，那么总和起来，是不是就是对nums[i..j]中的元素都加3了
        // 只要花费O(1)的时间修改diff数组，就相当于给nums的整个区间做了修改。多次修改diff，然后通过diff数组反推，即可得到nums修改后的结果。

        // 差分数组工具类
        static class Difference {
            // 差分数组
            int[] diff;

            // 输入一个初始数组，区间操作将在这个数组上进行
            public Difference(int[] nums) {
                assert nums.length > 0;
                diff = new int[nums.length];
                // 根据初始数组构造差分数组
                diff[0] = nums[0];
                for (int i = 1; i < nums.length; i++) {
                    diff[i] = nums[i] - nums[i - 1];
                }
            }

            // 给闭区间[i, j]增加val（可以是负数）
            public void increment(int i, int j, int val) {
                diff[i] += val;
                if (j + 1 < diff.length) {
                    diff[j + 1] -= val;
                }
            }

            // 返回结果数组
            public int[] result() {
                int[] res = new int[diff.length];
                // 根据差分数组构造结果数组
                res[0] = diff[0];
                for (int i = 1; i < diff.length; i++) {
                    res[i] = res[i - 1] + diff[i];
                }
                return res;
            }
        }
    }

    // 370. 区间加法
    // 给你输入一个长度为 n 的 nums 数组，其中的元素初始值都为 0，让你对其中的区间元素进行增减操作，最后返回最终的 nums 数组
    // 假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。
    // 其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex … endIndex]（包括 startIndex 和 endIndex）增加 inc。
    // 请你返回 k 次操作后的数组。
    // 示例: 输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] 输出: [-2,0,3,5,3]
    // 解释: 初始状态: [0,0,0,0,0] 进行了操作 [1,3,2] 后的状态: [0,2,2,2,0] 进行了操作 [2,4,3] 后的状态: [0,2,5,5,3] 进行了操作 [0,2,-2] 后的状态: [-2,0,3,5,3]
    static class GetModifiedArray {
        public int[] getModifiedArray(int length, int[][] updates) {
            // nums初始化
            int[] nums = new int[length];
            // 构造差分解法
            Difference df = new Difference(nums);
            for (int[] update : updates) {
                int i = update[0];
                int j = update[1];
                int val = update[2];
                df.increment(i, j, val);
            }
            return df.result();
        }

        static class Difference {
            // 差分数组
            int[] diff;

            public Difference(int[] nums) {
                assert nums.length > 0;
                diff = new int[nums.length];
                // 构造差分数组
                diff[0] = nums[0];
                for (int i = 1; i < nums.length; i++) {
                    diff[i] = nums[i] - nums[i - 1];
                }
            }

            // 给闭区间[i,j]增加val（可以是负数）
            public void increment(int i, int j, int val) {
                diff[i] += val;
                if (j + 1 < diff.length) {
                    diff[j + 1] -= val;
                }
            }

            public int[] result() {
                int[] res = new int[diff.length];
                // 根据差分数组构造结果数组
                res[0] = diff[0];
                for (int i = 1; i < diff.length; i++) {
                    res[i] = res[i - 1] + diff[i];
                }
                return res;
            }
        }
    }

    // 1109. 航班预定系统
    /*这里有 n 个航班，它们分别从 1 到 n 进行编号。
    有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi]
    意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
    请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
    示例 1：
    输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
    输出：[10,55,45,25,25]
    解释：
    航班编号        1   2   3   4   5
    预订记录 1 ：   10  10
    预订记录 2 ：       20  20
    预订记录 3 ：       25  25  25  25
    总座位数：      10  55  45  25  25
    因此，answer = [10,55,45,25,25]
    提示：
    1 <= n <= 2 * 104
    1 <= bookings.length <= 2 * 104
    bookings[i].length == 3
    1 <= firsti <= lasti <= n
    1 <= seatsi <= 104
    */

    // 这个题目就在那绕弯弯，其实它就是个差分数组的题，我给你翻译一下：
    // 给你输入一个长度为 n 的数组 nums，其中所有元素都是 0。再给你输入一个 bookings，里面是若干三元组 (i, j, k)，
    // 每个三元组的含义就是要求你给 nums 数组的闭区间 [i-1,j-1] 中所有元素都加上 k。请你返回最后的 nums 数组是多少？
    // 因为题目说的 n 是从 1 开始计数的，而数组索引从 0 开始，所以对于输入的三元组 (i, j, k)，数组区间应该对应 [i-1,j-1]。
    static class CorpFlightBookings {
        public int[] corpFlightBookings(int[][] bookings, int n) {
            // nums初始化为全0
            int[] nums = new int[n];
            // 构造差分数组
            Difference df = new Difference(nums);
            for (int[] booking : bookings) {
                // 注意转成数组索引要减1
                int i = booking[0] - 1;
                int j = booking[1] - 1;
                int val = booking[2];
                // 对区间nums[i..j]增加val
                df.increment(i, j, val);
            }
            // 返回最终的结果数组
            return df.result();
        }

        static class Difference {
            // 差分数组
            int[] diff;

            public Difference(int[] nums) {
                assert nums.length > 0;
                diff = new int[nums.length];
                // 构造差分数组
                diff[0] = nums[0];
                for (int i = 1; i < nums.length; i++) {
                    diff[i] = nums[i] - nums[i - 1];
                }
            }

            // 给闭区间[i, j]增加val（可以是负数）
            public void increment(int i, int j, int val) {
                diff[i] += val;
                if (j + 1 < diff.length) {
                    diff[j + 1] -= val;
                }
            }

            public int[] result() {
                int[] res = new int[diff.length];
                // 根据差分数组构造结果数组
                res[0] = diff[0];
                for (int i = 1; i < diff.length; i++) {
                    res[i] = res[i - 1] + diff[i];
                }
                return res;
            }
        }
    }

    // 1094. 拼车
    // 车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
    // 给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，
    // 接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
    // 当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
    // 示例 1：
    // 输入：trips = [[2,1,5],[3,3,7]], capacity = 4
    // 输出：false
    // 示例 2：
    // 输入：trips = [[2,1,5],[3,3,7]], capacity = 5
    // 输出：true
    static class CarPooling {
        // 比如输入：trips = [[2,1,5],[3,3,7]], capacity = 4
        // 相信你已经能够联想到差分数组技巧了：trips[i] 代表着一组区间操作，旅客的上车和下车就相当于数组的区间加减；
        // 只要结果数组中的元素都小于 capacity，就说明可以不超载运输所有旅客。
        // 但问题是，差分数组的长度（车站的个数）应该是多少呢？题目没有直接给，但给出了数据取值范围：
        // 0 <= trips[i][1] < trips[i][2] <= 1000
        // 车站编号从 0 开始，最多到 1000，也就是最多有 1001 个车站，那么我们的差分数组长度可以直接设置为 1001，这样索引刚好能够涵盖所有车站的编号：
        public boolean carPooling(int[][] trips, int capacity) {
            // 最多有1001个车站
            int[] nums = new int[1001];
            // 构造差分解法
            Difference df = new Difference(nums);
            for (int[] trip : trips) {
                // 乘客数量
                int val = trip[0];
                // 第trip[1]站乘客上车
                int i = trip[1];
                // 第trip[2]站乘客已经下车
                // 即乘客在车上的区间是[trip[1], trip[2]-1]
                int j = trip[2] - 1;
                // 进行区间操作
                df.increment(i, j, val);
            }
            int[] res = df.result();
            // 乘客自始至终都不应该超载
            for (int i = 0; i < res.length; i++) {
                if (capacity < res[i]) {
                    return false;
                }
            }
            return true;
        }

        // 差分数组工具类
        static class Difference {
            // 差分数组
            int[] diff;

            // 输入一个初始数组，区间操作将在这个数组上进行
            public Difference(int[] nums) {
                assert nums.length > 0;
                diff = new int[nums.length];
                // 根据初始数组构造差分数组
                diff[0] = nums[0];
                for (int i = 1; i < nums.length; i++) {
                    diff[i] = nums[i] - nums[i - 1];
                }
            }

            // 给闭区间[i,j]增加val（可以是负数）
            public void increment(int i, int j, int val) {
                diff[i] += val;
                if (j + 1 < diff.length) {
                    diff[j + 1] -= val;
                }
            }

            // 返回结果数组
            public int[] result() {
                int[] res = new int[diff.length];
                // 根据差分数组构造结果数组
                res[0] = diff[0];
                for (int i = 1; i < diff.length; i++) {
                    res[i] = res[i - 1] + diff[i];
                }
                return res;
            }
        }
    }
}
